package com.jlhlyby.string;

/**
 * 5. 最长回文子串
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * 示例 1：
 *
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 *
 * 输入: "cbbd"
 * 输出: "bb"
 */
public class LongestPalindrome {
    public static void main(String[] args) {
        String str = "babad";
        System.out.println(new LongestPalindrome().longestPalindrome(str));

    }
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i<s.length();i++){
            int length1 = expandAroundCenter(s,i,i); //奇数情况
            int length2 = expandAroundCenter(s,i,i+1);//偶数情况
            int subMax = Math.max(length1,length2);
            if (subMax > end - start ){
               start = i - (subMax-1)/2;
               end = i+subMax/2;
            }
        }
        return s.substring(start,end+1);
    }
    //通过中心来往两侧比较，算出最大长度
    public int expandAroundCenter(String s,int left,int right){
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        return right - left - 1;
    }
}
